|
In the mathematical discipline of graph theory, 2-factor theorem discovered by Julius Petersen, is one of the earliest works in graph theory and can be stated as follows: : 2-factor theorem. Let ''G'' be 2''k''-regular graph, then ''E''(''G'') can be decomposed into the union of ''k'' line-disjoint 2-factors.〔Lovász, László, and Plummer, M.D.. ''Matching Theory'', American Mathematical Soc., Jan 1, 2009. Print〕 ==Proof== In order to prove this generalized form of the theorem, Petersen first proved that a 4-regular graph can be factorized into two 2-factors by taking alternate edges in a eulerian trial. He noted that the same technique used for the 4-regular graph yields a factorization of a 2''k''-regular graph into two ''k''-factors.〔Mulder, H. "Julius Petersen’s theory of regular graphs". ''Discrete Mathematics'', 100 (1992) 157-175 North-Holland〕 To prove this theorem, first we remark that it is sufficient to consider connected graphs. A connected graph with even degree has an Euler trial. Traversing this Euler trial we get an orientation ''D'' of ''G'' such that every point has indegree and outdegree = ''k''. Then we replace every point ''v'' ϵ ''V''(''D'') by two points ''v’'', ''v”'', and for every directed line ''uv'' ϵ ''E''(''D'') we draw in one line from ''u’'' to ''v”''. Since ''D'' has in- and outdegree equal to ''k'' the resulting bigraph ''G’'' is ''k''-regular. The lines of ''G’'' can be decomposed into ''k'' perfect matchings. Now if we identify ''v’'' and ''v”'' for every ''v'', we recover the graph ''G'', and these ''k'' perfect matchings of ''G’'' will be mapped onto ''k'' 2-factors of ''G'' which partition the lines.() In other words, for the general case the factorization of a 2''k''-regular graph into two factors is an easy consequence of Euler’s theorem: By applying the same argument to each component, we may assume that G is connected and 2''k''-regular with vertices ''v''1, ..., ''v''''n''. Let ''C'' be an Eulerian circuit of ''G'', followed in a particular direction. Then use Eulerian circuit of ''G'' to create an supplementary ''k''-regular bipartite graph H, such that a perfect matching in ''H'' corresponds to a 2-factor in ''G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「2-factor theorem」の詳細全文を読む スポンサード リンク
|